//
// Description: 5852. 最小化目标值与所选元素的差
// Created by Loading on 2021/8/22.
//

#include <bits/stdc++.h>

using namespace std;

int minimizeTheDifference(vector<vector<int>> &mat, int target) {
    // 使用 bitset，将第 0 位置为 1
    // bs 存储每一行与之前进行相加运算后的所有结果，第 i 位为 1 表示可以达到结果 i，i 从 0 开始
    bitset<4901> bs(1);
    for(auto &v : mat) {
        bitset<4901> temp;
        for(auto &x : v) {
            /* 关键代码，遍历每一行，将 bs 左移 x 位，与 temp 做或运算，结果就是 x 与上一行每一个结果求和 */
            temp |= bs << x;
        }
        // 二维转变一维
        bs = temp;
    }

    int res = INT_MAX;
    for (int i = 0; i < 4901; ++i) {
        if (bs[i]) {
            res = min(res, abs(target - i));
        }
    }

    return res;
}

int main() {
    vector<vector<int>> mat = {{1, 2, 3},
                               {4, 5, 6},
                               {7, 8, 9}};
    int target = 13;
    int res = minimizeTheDifference(mat, target);
    cout << res << endl;
    return 0;
}